package com.Sep_Twellve;

import com.Sep_Five.Solution101;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution106 {
    public Solution101.TreeNode buildTree(int[] inorder, int[] postorder) {
        return dfs(0,inorder.length-1,0,postorder.length-1,inorder,postorder);
    }

    public Solution101.TreeNode dfs(int leftin, int rightin, int leftpost,int rightpost,int[] inorder,int[] postorder)
    {
        if (leftin>rightin) return null;
        Solution101.TreeNode root=new Solution101.TreeNode(postorder[rightpost]);
        int rootin=leftin;
        while (rootin<=rightin&&inorder[rootin]!=postorder[rightpost]) rootin++;
        int left=rootin-leftin;
        root.left=dfs(leftin,rootin-1,leftpost,leftpost+left-1,inorder,postorder);
        root.right=dfs(rootin+1,rightin,leftpost+left-1,rightpost-1,inorder,postorder);
        return root;
    }
}
